package 中等.贪心思想;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三
 * 个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k
 * 和 nums[i] < nums[k] < nums[j] 。
 * 如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/132-pattern
 */
public class 模式132_456 {

    public static void main(String[] args) {

        System.out.println(find132pattern2(new int[]{1, 4, 2}));

    }

    /**
     * 枚举 i （超时）
     *
     * @param nums
     * @return
     */
    public static boolean find132pattern(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int j = i + 1;
            // 找到第一个 > nums[i] 的 j 索引
            while (j < nums.length && nums[j] < nums[i]) {
                // 有比 i 小的数，优先选择较小的 i
                i = j;
                j++;
            }

            for (int k = j + 1; k < nums.length; k++) {
                if (nums[k] < nums[j] && nums[k] > nums[i]) {
                    return true;
                }
                if (nums[k] > nums[j]) {
                    // 优先选择较大的 j
                    j = k;
                }
            }
        }

        return false;
    }

    /**
     * 逆序遍历维护一个单调递减的栈
     * 栈顶元素逆序遍历当前的最大元素，作为 j ，弹出的元素比栈顶元素小
     * 使用一个变量 k 存储起来，已经有了 j > k ，那么弹出的元素尽可能
     * 选择较大的元素，使得 k > i
     * 特别的，我们将 k 初始化为最小值，如果遍历到 nums[i] < nums[k]
     * 说明栈顶一定存在一个 nums[j] > nums[k]
     */
    public static boolean find132pattern2(int[] nums) {
        int numK = Integer.MIN_VALUE;
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] < numK) {
                return true;
            }

            while (!stack.isEmpty() && stack.peekFirst() < nums[i]) {
                numK = Math.max(numK, stack.pollFirst());
            }
            stack.addFirst(nums[i]);
        }

        return false;
    }

}
